//AVL TREE TESTED ON LIGHT OJ
#define S int
#define T int
#define MAX_SIZE 1000000
typedef struct {
    S key;
    T value;
    int size,height;
    int child[2];
}node;
node list[MAX_SIZE];
int size;
int balance(int );
int cmp(const void *a, const void *b) {
    return *((int*)a) - *((int*)b);
}
#define sz(t) (t ? list[t].size : 0 )
#define ht(t) (t ? list[t].height : 0 )
int rotate(int t,int l, int r) {
    int s=list[t].child[r];
    list[t].child[r]=list[s].child[l];
    list[s].child[l]=balance(t);

    if (t)list[t].size=sz(list[t].child[0])+sz(list[t].child[1])+1;
    if (s)list[s].size=sz(list[s].child[0])+sz(list[s].child[1])+1;
    return balance(s);
}
int balance(int t) {
    int i;
    for (i=0;i<2;++i) {
        if ( ht(list[t].child[!i]) - ht(list[t].child[i] )< -1 ) {
            if (ht(list[list[t].child[i]].child[!i])-ht(list[list[t].child[i]].child[i])>0)
                list[t].child[i]=rotate(list[t].child[i],i,!i);

            return rotate(t,!i,i);
        }
    }
    if (t)list[t].height=max( ht(list[t].child[0]),ht(list[t].child[1]))+1;
    if (t)list[t].size=sz(list[t].child[0])+ sz(list[t].child[1])+1;
    return t;
}
int move_down(int t,int rhs) {
    if (t==0)return rhs;
    list[t].child[1]=move_down(list[t].child[1],rhs);
    return balance(t);
}
int find(int t, const S* key) {
    if (t==0)return 0;
    int res = cmp(key, &list[t].key);
    if (res==0)return t;
    if (res<0)return find(list[t].child[0],key);
    return find(list[t].child[1],key);
}
int erase(int t, const S* key) {
    if (t==0)return 0;
    int res = cmp(key, &list[t].key);
    if (res==0)return move_down(list[t].child[0],list[t].child[1]);
    if (res<0)list[t].child[0]=erase(list[t].child[0],key);
    else
        list[t].child[1]=erase(list[t].child[1],key);
    list[t].size--;
    return balance(t);
}
int insert2(int t, int x) {
    if (t==0)return x;
    if (cmp(&list[x].key,&list[t].key)<=0)list[t].child[0]=insert2(list[t].child[0],x);
    else
        list[t].child[1]=insert2(list[t].child[1],x);
    list[t].size++;
    return balance(t);
}
int insert(int root, const S* key, const T* value) {
    ++size;
    list[size].size = list[size].height=1;
    memcpy(&list[size].key,key,sizeof(S));
    memcpy(&list[size].value,value,sizeof(T));
    return insert2(root,size);
}
int rank(int t, int k) {
    if (!t)return 0;
    int m = sz(list[t].child[0]);
    if (k<m)return rank(list[t].child[0],k);
    if (k==m)return t;
    return rank(list[t].child[1],k-m-1);
}
int t[MAX_SIZE*2];
    